package com.s5.recursion;

public class Example1 {

	public static void main(String[] args) {
		System.out.println(f(5));

		System.out.println("-----step-----");
		// 1,1,1 1,2 2,1
		System.out.println(step(3));
		// 1,1,1,1 1,1,2 1,2,1 2,1,1 2,2
		System.out.println(step(4));

		System.out.println("-----fibonacci-----");
		System.out.println(fibonacci(2));
		System.out.println(fibonacci(3));
		System.out.println(fibonacci(4));
		System.out.println(fibonacci(5));
		System.out.println(fibonacci(6));

		System.out.println("-----factorial-----");
		System.out.println(factorial(1));
		System.out.println(factorial(2));
		System.out.println(factorial(3));
		System.out.println(factorial(4));
		System.out.println(factorial(5));
		
		Integer[] array = {1, 2, 3, };
		fullArray(array, 0);

		
	}

	/**
	 * 只知道前排是第几排，求当前座位在第几排
	 */
	static int f(int n) {
		// 已知 f（1） = 1;
		if (n == 1) {
			return 1;
		}
		// f(n)=f(n-1)+1
		return f(n - 1) + 1;
	}

	/**
	 * 每次只能上 1或2阶台阶，求上n阶台阶有多少种走法
	 */
	static int step(int n) {
		// 已知 f（1） = 1;f(n)=f(n-1)+1
		if (n == 1) {
			return 1;
		}
		if (n == 2) {
			return 2;
		}
		return f(n - 1) + f(n - 2);
	}

	/**
	 * 求斐波拉契数列 F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
	 */
	static int fibonacci(int n) {
		if (n == 0) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}
		return fibonacci(n - 1) + fibonacci(n - 2);
	}

	/**
	 * 求阶乘
	 */
	static int factorial(int n) {
		// 已知 f（0） = 1;
		if (n == 0) {
			return 1;
		}
		return factorial(n - 1) * n;
	}
	
	static void swap(Integer[] array, int i, int j) {
		// System.out.println("i = " + i + ", j = " + j);
		if (i != j) {
			Integer t = array[i];
		    array[i] = array[j];
		    array[j] = t;
		}
	}
	
	/* 
	 * 递归输出序列的全排列
	 */
	static void fullArray(Integer[] array, int index) {
		// System.out.println("index = " + index + ", arraySize = " + array.length);
		int arraySize = array.length;
		if (index == arraySize) {
			// System.out.println("index == arraySize: " + index + "== " + arraySize);
	        for(int i = 0; i < arraySize; ++i) {
	        	System.out.print(array[i]);
	        	System.out.print(' ');
	        }
        	System.out.println();
	    } else if(index < arraySize) {
	    	// System.out.println("index < arraySize: " + index + "< " + arraySize);
		    for(int i = index; i < arraySize; ++i) {
		        swap(array, i, index);
		        fullArray(array, index + 1);
		        // 调用结束之后还需要回溯将交换位置的元素还原，以供其他下降路径使用
		        swap(array, i, index);
		    }
	    }
	}

}
